1. Field of the Invention
The present invention relates to an operation device and operation method for Discrete Cosine Transform (hereinafter referred to as DCT) and inverse Discrete Cosine Transform (hereinafter referred to as inverse DCT) used for high efficiency coding of image data in video phone system, TV conference system, and digital VTR.
2. Description of the Related Art
DCT is a method for transforming discrete data such as image information (hereinafter referred to as original image data) into discrete data in the frequency space (hereinafter referred to as DCT results) by using the cosine function. It is executed by product-sum operation of the original image data and DCT coefficients, and DCT results are obtained as the result of such operation. Inverse DCT is an inverse transform of the above DCT. It is executed by product-sum operation of the DCT results and inverse DCT coefficients, and the original image data can be obtained as a result of such inverse DCT. When the number of data is N, one-dimensional DCT and inverse DCT is referred to as N-order one-dimensional DCT or N-order one-dimensional inverse DCT, or one-dimensional N-order DCT and one-dimensional N-order inverse DCT.
Supposing the original image data in N order one-dimensional DCT and inverse DCT to be x (i; N) and the DCT results to be y (k; N), the relationship between y (k; N) and x (i; N) are expressed by the following formulae (1) and (2) respectively. Note that 0 .ltoreq.i &lt;N and 0 .ltoreq.k &lt;N here. EQU y (k; N)=x(i; N) d(i, k; N) i (1) EQU x (i; N)=f(i, k; N) y(k; N) k (2) ##EQU1##
In the formulae, the sum or accumulation for variable i is described as " i". Further, d(i, k; N) is the DCT coefficient and f (i, k; N) is the inverse DCT coefficient. The formula (1) above represents the DCT operation and (2) the inverse DCT operation.
When the original image data are x (i, j; N) and DCT results are y (k, l; N) for N-order two-dimensional DCT and inverse DCT, the relationship between y (k, l; N) and x (i, j; N) can be expressed by the following formulae (3) and (4). Note that 0 .ltoreq.i &lt;N, 0 .ltoreq.j &lt;N and 0 .ltoreq.1 &lt;N here. EQU y (k,l;N)=d(j,l;N)x(i,j; N)d(i,k;N) .vertline.i,j (3) EQU x (i,j;N)=f(i,k;N) y(k,l;N)f(i,j;N) .vertline.k,l (4)
As seen from the above formulae (3) and (4), N-order two-dimensional DCT and inverse DCT can be executed by performing 2N times the same product-sum operation as N-order one-dimensional DCT and inverse DCT.
In high-efficiency coding whose purpose is a significant reduction in the amount of original image data, the above two-dimensional DCT and two-dimensional inverse DCT are used together with motion vector detection and FIR filter and quantization for data compression. Recommended standardization methods for high-efficiency coding such as MPEG and CCITT-H. 261 specify the image data subjected to the transform to be 8.times.8 pixels. In other words, it is necessary to execute two-dimensional eight-order DCT and two-dimensional eight-order inverse DCT to realize such a standardization method.
The above DCT transform formulae may be calculated directly. This is referred to as the first conventional operation method. In the first conventional operation method, the operation amount includes N.sup.2 times of product-sum operation for one-dimensional N-order DCT and inverse DCT and 2N.sup.3 times of product-sum operation for two dimensional N-order DCT and inverse DCT. When an operation device adopts the first operation method, even if one cycle is sufficient for one product-sum operation, it takes 1024 cycles to execute two-dimensional eight order DCT and inverse DCT. Thus, in the first conventional operation method, processing cycle increases in the order of N.sup.3. For example, to execute two-dimensional eight order DCT and inverse DCT, it takes a long processing time representing substantially half of the high-efficiency coding period.
To solve such problem, high-speed algorithm to reduce the operation amount for DCT and inverse DCT have been developed from the 1970s, and exclusive devices for DCT and inverse DCT operation using such high-speed algorithms have been invented. Such high-speed algorithms utilize symmetry and asymmetry properties of the cosine function to reduce the operation amount for DCT and inverse DCT. Such a DCT and inverse DCT operation methods based on the high-speed algorithms are the second conventional operation method. A DCT and inverse DCT operation device according to a high-speed algorithm FCT method executing such second conventional operation method has been disclosed by Byeong Gi Lee in November 1984 in IEEE Transaction Acoustics, Speech and Signal Processing, Vol. 32, No. 6, pp. 1243 as briefly shown in FIG. 7.
FIG. 7 is a block diagram to show the configuration of eight-order DCT and inverse DCT operation device according to the high-speed algorithm FCT method. The operation device comprises adders 710, 720, 730 and 740 and multipliers 760, 770 and 780 disposed alternately. Execution of operation procedures based on the algorithm of the FCT method with this device enables high-speed DCT and inverse DCT operations.
Thus, a DCT and inverse DCT operation device using the second conventional operation method enables DCT and inverse DCT operations at a higher speed than that with the first conventional operational method. However, it has the following drawbacks:
(1) The operation device using the second conventional operation method requires much hardware. PA1 (2) Its special configuration prevents utilization for high-efficiency coding processes other than DCT and inverse DCT operations. PA1 (3) It lacks flexibility since the number of adders and multipliers required and their configuration vary depending on the order of for DCT and inverse DCT.
Therefore, it is difficult to provide a smaller and less expensive high-efficiency coding device to be used in TV conference systems and video phone systems.